package com.zhang.sort;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * @author zhang
 * @time 2022/01/12 08:58:04
 */
public class BucketSort {
    public void sort(int[] array,int numberOfBuckets) {
        List<List<Integer>> buckets = createBuckets(array, numberOfBuckets);
        int i = 0;
        for (List<Integer> bucket : buckets) {
            Collections.sort(bucket);
            for (Integer item : bucket) {
                array[i++] = item;

            }
        }
    }

    private List<List<Integer>> createBuckets(int[] array,int numberOfBuckets) {
        List<List<Integer>> buckets = new ArrayList<>();
        for (int i = 0; i < numberOfBuckets; i++) {
            buckets.add(new ArrayList<>());
        }
        for (int item : array) {
            buckets.get(item / numberOfBuckets).add(item);


        }
        return buckets;
    }
}
